package main.Q501_600;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Q581_590 {
    public static void main(String[] args) {
        System.out.println("Question581：最短无序连续子数组");
        System.out.println("Question582：");
        System.out.println("Question583：两个字符串的删除操作");
        System.out.println("Question584：");
        System.out.println("Question585：");
        System.out.println("Question586：");
        System.out.println("Question587：");
        System.out.println("Question588：");
        System.out.println("Question589：N叉树的前序遍历");
        System.out.println("Question590：N叉树的后序遍历");
    }
}

class Question581{
    public int findUnsortedSubarray(int[] nums) {//与已经排序的数组比较不同的点
        int n = nums.length;
        int[] arr = nums.clone();
        Arrays.sort(arr);
        int i = 0, j = n - 1;
        while (i <= j && nums[i] == arr[i]) i++;
        while (i <= j && nums[j] == arr[j]) j--;
        return j - i + 1;
    }
}

class Question583{
    public int minDistance(String word1, String word2) {//求出最长公共子序列长度，公共子序列与两字符串长度差即为最少步数
        int count=0,length1=word1.length(),length2=word2.length(),maxLength=0;
        int[][] dp=new int[length1+1][length2+1];
        char[] str1=word1.toCharArray(),str2=word2.toCharArray();
        for (int i=0;i<length1+1;i++){
            for (int j=0;j<length2+1;j++){
                if(i==0||j==0) dp[i][j]=0;
                else {
                    if (str1[i-1]==str2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
                    else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
                maxLength=Math.max(maxLength,dp[i][j]);
            }
        }
        if (maxLength!=0){
            count+=length1-maxLength;
            count+=length2-maxLength;
        }else count=length1+length2;
        return count;
    }
}

class Question589{
    public void process(Node root,List<Integer> list){
        if (root==null) return;
        list.add(root.val);
        for (Node cur: root.children) process(cur,list);
    }
    public List<Integer> preorder(Node root) {
        List<Integer> list=new ArrayList<>();
        process(root,list);
        return list;
    }
}

class Question590{
    public void process(Node root,List<Integer> list){
        if (root==null) return;
        for (Node cur: root.children) process(cur,list);
        list.add(root.val);
    }
    public List<Integer> postorder(Node root) {
        List<Integer> list=new ArrayList<>();
        process(root,list);
        return list;
    }
}